package src.算法.希尔排序;

public class Sheller {
    public static void sort(Comparable[] a){
        // 1.根据数组a的长度确定h的增长量
        int h = 1;
        while (h<a.length/2){
            h = 2*h + 1;
        }
        // 2.希尔排序
        while (h>=1){
            // 找到待插入的元素
            for (int i = h; i < a.length; i++) {
                // 把待插入数插入到有序序列【假设第一个数为有序的】中
                for (int j = i; j >= h; j-=h) {
                    // 待插入的元素a[j],a[j-h]>a[j]则交换位置
                    if(greater(a[j-h],a[j])){
                        exch(a,j-h,j);
                    }else {
                        break;
                    }
                }
            }
            //
            // 减少h的值
            h/=2;
        }
    }
    // 比较前一个元素是否大于后一个元素
    private static boolean greater(Comparable a,Comparable b){
        int result = a.compareTo(b);
        return result>0;
    }
    // 数组元素i和j交换位置
    private static void exch(Comparable[] a,int i,int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
